package q18_fourSum;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{0,0,0,1000000000,1000000000,1000000000,1000000000},1000000000));

    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        if(len < 4){
            return res;
        }
        // 注意 i < len - 3 即可，因为已经排序
        for (int i = 0; i < len - 3; i++) {
            // 确定第一个数 nums[i]
            if((i != 0)&&(nums[i] == nums[i - 1])){
                continue;
            }

            if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target){
                // 最小的四个数大于target 结束循环
                break;
            }
            if((long)nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target){
                // 确定的数nums[i] 加上最大的三个数仍然小于target，则需要进入nums[i + 1]
                continue;
            }

            // 同样的 j < len - 2 即可
            for (int j = i + 1; j < len - 2; j++) {
                // 确定第二个数nums[j]

                if((j != (i + 1))&&(nums[j] == nums[j - 1])){
                    continue;
                }

                if((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target){
                    // 最小的四个数大于target 结束第二重循环
                    break;
                }
                if((long)nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target){
                    // 确定的数nums[i] nums[j] 加上最大的两个数仍然小于target，则需要进入nums[j + 1]
                    continue;
                }

                int p3 = j + 1;
                int p4 = len - 1;

                while(p3 < p4){
                    if(nums[i] + nums[j] + nums[p3] + nums[p4] > target){
                        p4--;
                    }else if(nums[i] + nums[j] + nums[p3] + nums[p4] < target){
                        p3++;
                    }else if(nums[i] + nums[j] + nums[p3] + nums[p4] == target){
                        res.add(new ArrayList<>(List.of(nums[i] , nums[j] , nums[p3] , nums[p4])));
                        p3++;
                        p4--;
                        while((nums[p3] == nums[p3 - 1]) && (p3 < p4)){
                            p3++;
                        }
                        while((nums[p4] == nums[p4 + 1]) && (p3 < p4)){
                            p4--;
                        }
                    }

                }

            }


        }
        return res;
    }
}
